package com.cqs.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }


    public static String preOrderPrint(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        List<Integer> list = preOrder(root);
        if (list.size() > 0) {
            sb.append(list.get(0));
            for (int i = 1; i < list.size(); i++) {
                sb.append("-->"  +list.get(i));
            }
        }
        return sb.toString();
    }

    public static List<Integer> preOrder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        stack.push(node);
        while (!stack.isEmpty()) {
            node = stack.pop();
            list.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return list;
    }

    public static String inOrderPrint(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        String sep = "-->";
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            sb.append(node.val + sep);
            node = node.right;
        }
        for (int i = 0; i < sep.length(); i++) {
            sb.deleteCharAt(sb.length() - 1);
        }
        System.out.println(sb.toString());
        return sb.toString();
    }

    public static List<Integer> inOrder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            list.add(node.val);
            node = node.right;
        }
        return list;
    }

}